package leetcode.code1728;

public class Solution2 extends Solution1728 {
	int rows;
	int cols;
	int[][] grids;

	int ROAD = 1, WALL = 0, CAT = 2, MOUSE = 3, FOOD = 4;
	int jumpCat;
	int jumpMouse;
	int XFOOD;
	int YFOOD;

	boolean WINMOUSE = true;
	boolean WINCAT = false;
	boolean[][] cat2, mouse2;
//	Boolean[][][][] seen;
	@Override
	public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
		this.jumpCat = catJump;
		this.jumpMouse = mouseJump;
		rows = grid.length;
		cols = grid[0].length();
		grids = new int[rows][cols];
		int xmouse = 0, ymouse = 0;
		int xcat = 0, ycat = 0;
		for (int i = 0; i < rows; i++) {
			char[] g = grid[i].toCharArray();
			for (int j = 0; j < cols; j++) {
				char c = g[j];
				if (c == '.') {
					grids[i][j] = ROAD;
				} else if (c == '#') {
					grids[i][j] = WALL;
				} else if (c == 'C') {
					grids[i][j] = CAT;
					xcat = i;
					ycat = j;
				} else if (c == 'M') {
					grids[i][j] = MOUSE;
					xmouse = i;
					ymouse = j;
				} else if (c == 'F') {
					grids[i][j] = FOOD;
					this.XFOOD = i;
					this.YFOOD = j;
				}
			}
		}
//		seen = new Boolean[rows][cols][rows][cols];
		cat2 = new boolean[rows][cols];
		mouse2 = new boolean[rows][cols];
		cat2[xcat][ycat] = true;
		mouse2[xmouse][ymouse] = true;
//		H.printObject(grids);
		return this.mouseMove(0, xmouse, ymouse, xcat, ycat);
	}

	private boolean mouseMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
//		if (seen[xmouse][ymouse][xcat][ycat] != null) {
//			return seen[xmouse][ymouse][xcat][ycat];
//		}
		if ((xmouse == xcat && ymouse == ycat) || (round == 1000)) {
//			seen[xmouse][ymouse][xcat][ycat] = this.WINCAT;
			return this.WINCAT;
		}
		if (XFOOD == xmouse && YFOOD == ymouse) {
//			seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
			return this.WINMOUSE;
		}
		boolean ans = this.WINCAT;
		// 向上
		for (int i = 1; i <= this.jumpMouse; i++) {
			if (xmouse - i >= 0) {
				if (this.grids[xmouse - i][ymouse] != WALL && !mouse2[xmouse - i][ymouse]) {
					mouse2[xmouse - i][ymouse] = true;
					ans = this.catMove(round, xmouse - i, ymouse, xcat, ycat);
					mouse2[xmouse - i][ymouse] = false;
					if (ans == this.WINMOUSE) {
//						seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向下
		for (int i = 1; i <= this.jumpMouse; i++) {
			if (xmouse + i < this.rows) {
				if (this.grids[xmouse + i][ymouse] != WALL && !mouse2[xmouse + i][ymouse]) {
					mouse2[xmouse + i][ymouse] = true;
					ans = this.catMove(round, xmouse + i, ymouse, xcat, ycat);
					mouse2[xmouse + i][ymouse] = false;
					if (ans == this.WINMOUSE) {
//						seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向左
		for (int i = 1; i <= this.jumpMouse; i++) {
			if (ymouse - i >= 0) {
				if (this.grids[xmouse][ymouse - i] != WALL && !mouse2[xmouse][ymouse - i]) {
					mouse2[xmouse][ymouse - i] = true;
					ans = this.catMove(round, xmouse, ymouse - i, xcat, ycat);
					mouse2[xmouse][ymouse - i] = false;
					if (ans == this.WINMOUSE) {
//						seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向右
		for (int i = 1; i <= this.jumpMouse; i++) {
			if (ymouse + i < this.cols) {
				if (this.grids[xmouse][ymouse + i] != WALL && !mouse2[xmouse][ymouse + i]) {
					mouse2[xmouse][ymouse + i] = true;
					ans = this.catMove(round, xmouse, ymouse + i, xcat, ycat);
					mouse2[xmouse][ymouse + i] = false;
					if (ans == this.WINMOUSE) {
//						seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
//		seen[xmouse][ymouse][xcat][ycat] = this.WINCAT;
		return ans;
	}

	private boolean catMove(int round, int xmouse, int ymouse, int xcat, int ycat) {
//		if (seen[xmouse][ymouse][xcat][ycat] != null) {
//			return seen[xmouse][ymouse][xcat][ycat];
//		}
		if ((xmouse == xcat && ymouse == ycat) || (XFOOD == xcat && YFOOD == ycat)) {
//			seen[xmouse][ymouse][xcat][ycat] = WINCAT;
			return this.WINCAT;
		}
		boolean ans = this.WINMOUSE;
		// 向上
		for (int i = 1; i <= this.jumpCat; i++) {
			if (xcat - i >= 0) {
				if (this.grids[xcat - i][ycat] != WALL && !cat2[xcat - i][ycat]) {
					cat2[xcat - i][ycat] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat - i, ycat);
					cat2[xcat - i][ycat] = false;
					if (!ans) {
//						seen[xmouse][ymouse][xcat][ycat] = WINCAT;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向下
		for (int i = 1; i <= this.jumpCat; i++) {
			if (xcat + i < this.rows) {
				if (this.grids[xcat + i][ycat] != WALL && !cat2[xcat + i][ycat]) {
					cat2[xcat + i][ycat] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat + i, ycat);
					cat2[xcat + i][ycat] = false;
					if (!ans) {
//						seen[xmouse][ymouse][xcat][ycat] = WINCAT;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向左
		for (int i = 1; i <= this.jumpCat; i++) {
			if (ycat - i >= 0) {
				if (this.grids[xcat][ycat - i] != WALL && !cat2[xcat][ycat - i]) {
					cat2[xcat][ycat - i] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat, ycat - i);
					cat2[xcat][ycat - i] = false;
					if (!ans) {
//						seen[xmouse][ymouse][xcat][ycat] = WINCAT;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
		// 向右
		for (int i = 1; i <= this.jumpCat; i++) {
			if (ycat + i < this.cols) {
				if (this.grids[xcat][ycat + i] != WALL && !cat2[xcat][ycat + i]) {
					cat2[xcat][ycat + i] = true;
					ans = this.mouseMove(round + 1, xmouse, ymouse, xcat, ycat + i);
					cat2[xcat][ycat + i] = false;
					if (!ans) {
//						seen[xmouse][ymouse][xcat][ycat] = WINCAT;
						return ans;
					}
				} else {
					break;
				}
			} else {
				break;
			}
		}
//		seen[xmouse][ymouse][xcat][ycat] = this.WINMOUSE;
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();

	}

}
